/*
 * Copyright (C), 2015-2018
 * FileName: Solution074
 * Author:   zhao
 * Date:     2018/12/20 10:14
 * Description: 74. 搜索二维矩阵
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

/**
 * 〈一句话功能简述〉<br>
 * 〈74. 搜索二维矩阵〉
 *
 * @author zhao
 * @date 2018/12/20 10:14
 * @since 1.0.1
 */
public class Solution074 {
    /**************************************
     * 题目
     编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

     每行中的整数从左到右按升序排列。
     每行的第一个整数大于前一行的最后一个整数。
     示例 1:

     输入:
     matrix = [
     [1,   3,  5,  7],
     [10, 11, 16, 20],
     [23, 30, 34, 50]
     ]
     target = 3
     输出: true
     示例 2:

     输入:
     matrix = [
     [1,   3,  5,  7],
     [10, 11, 16, 20],
     [23, 30, 34, 50]
     ]
     target = 13
     输出: false
     **************************************/

    /*************************************
     想法：
     1. 先编历第一列的数据，找到那个比target大的数据，那么target在这一项的前一行(遍历1/10/23)
     在关键行使用二分查找
     2.陈独秀方法，把二维数组转换成一个一维数组，直接上二分查找
     坐标转换：matrix[i][j]  <=> matrix[a]   其中a=i*n+j， i=a/n,  j=a%n;

     我的做法
     超过98%的测试案例
     时间复杂度/空间复杂度：n/1
     代码执行过程：

     总结：

     ************************************/
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] > target) {
            return false;
        }
        int muchTargetIndex = -1;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == target) {
                return true;
            } else if (matrix[i][0] > target) {
                muchTargetIndex = i - 1;
                break;
            } else {
                muchTargetIndex++;
            }
        }

        int left = 0;
        int right = matrix[muchTargetIndex].length - 1;
        int center = 0;
        while (left <= right) {
            center = left + (right - left) / 2;
            if (matrix[muchTargetIndex][center] == target) {
                return true;
            } else if (matrix[muchTargetIndex][center] > target) {
                right = center - 1;
            } else {
                left = center + 1;
            }
        }

        return false;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public boolean better(int[][] matrix, int target) {
        if(matrix.length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0, high = m * n;
        while(low < high){
            int mid = (low + high) / 2;
            if(matrix[mid / n][mid % n] == target){
                return true;
            }else if(matrix[mid / n][mid % n] < target){
                low = mid + 1;
            }else{
                high = mid;
            }
        }
        return false;
    }
}
